"""
本模块提供一个函数 read_graph，用于以邻接矩阵方式读取旅行商问题中的图。
"""
__all__ = (
    'read_graph',
    'AdjacencyMatrix',
)

import re
from typing import List

RE_STRIP = re.compile(r'^\s+|\s+$')
RE_WHITESPACE = re.compile(r'\s+')

AdjacencyMatrix = List[List[int]]

def advanced_strip(x: str) -> str:
    """
    高级版 strip。本函数把字符串两端的空格去除，将中间的多个空格合并为一个。
    :param x: 字符串
    :return: 去除首尾空格，合并中间空格后的字符串
    """
    x = RE_STRIP.sub('', x)
    x = RE_WHITESPACE.sub(' ', x)
    return x


def read_graph(directed: bool = False) -> AdjacencyMatrix:
    """
    读取旅行商问题中的图。

    该函数首先读取一个数字 city_num，表示城市个数；
    随后读取 city_num 行，每行 city_num 个数字，
    第 i 行的第 j 个数字（从 0 起计数）表示城市 i 到 j（从 0 起计数）的距离。

    :return: 表示城市距离的邻接矩阵
    """
    city_num = int(advanced_strip(input('城市个数: ')))
    result: List[List[int]] = []

    for i in range(city_num):
        city_distance_input = advanced_strip(input()).split(' ')
        if len(city_distance_input) != city_num:
            raise ValueError('输入的数字个数与城市个数不一致')

        result.append([int(x) for x in city_distance_input])

    # 打一个空行
    print('')

    # 将自己到自己的距离统一设为 0
    for i in range(city_num):
        result[i][i] = 0

    # 如果是无向图，检验两个方向的距离是否一致
    if not directed:
        for i in range(city_num):
            for j in range(i, city_num):
                if result[i][j] != result[j][i]:
                    raise ValueError(f'\n城市 {i} 到城市 {j} 的距离为 {result[i][j]}，'
                                     f'而城市 {j} 到城市 {i} 的距离为 {result[j][i]}，'
                                     f'当前所输入的是无向图，但距离不一致。\n')

    return result
